\chapter[Graph Theory \\ \textnormal{\emph{Lectured in Michaelmas \oldstylenums{2022} by \textsc{Dr.\ J.\ Sahasrabudhe}}}]{Graph Theory}
\emph{\Large Lectured in Michaelmas \oldstylenums{2022} by \textsc{Dr.\ J.\ Sahasrabudhe}}

A graph is a set of vertices, each pair of which may be joined with an edge.
The fact that graphs can be used to model any symmetric relation makes them widely applicable to various areas of mathematics such as knot theory.

We begin by studying various notions of connectivity of graphs, and then discuss planarity.
The famous four-colour theorem states that a planar graph can be drawn using only four colours for the vertices, such that no two joined vertices share the same colour.
While the proof of this theorem is extremely long, we prove the five-colour theorem and related results about graphs on other surfaces.

As graphs grow, we are interested in their asymptotic behaviour.
For example, how many edges must there be in a graph before we can guarantee that there is a triangle?
We study various properties of this form, and prove sufficient conditions to see certain behaviour in any given graph.
We also use probability theory to provide bounds on how likely certain events in a random graph are to occur.

\subfile{../../ii/graph/main.tex}
